#include "LinkList.h"
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 初始化链表
int list_init(LList **list, const size_t size) {
  // 开辟空间
  *list = malloc(sizeof(LList));
  if (*list == NULL) {
    return -1;
  }
  (*list)->head_ptr = NULL;
  (*list)->tail_ptr = NULL;
  (*list)->size = size;
  (*list)->nmemb = 0;
  return 1;
}
// 内部函数：创建节点
static LNode *__create_node(const void *data, size_t size) {
  // 为节点开辟空间
  LNode *node = malloc(sizeof(LNode));
  // 判断开辟空间是否成功
  if (node == NULL) {
    return NULL;
  }
  // 为节点中的数据开辟空间
  node->data = malloc(size);
  // 判断开辟空间是否成功
  if (node->data == NULL) {
    free(node);
    node = NULL;
    return NULL;
  }
  memcpy(node->data, data, size);
  node->next = NULL;
  node->prior = NULL;
  return node;
}

/*
int list_insert(LList *list, size_t index, const void *new_data) {
  LNode *new_node;
  if ((new_node = __create_node(new_data, list->size)) == NULL) {
    return -1;
  }
}
*/

int list_insert_front(LList *list, const void *new_data) {
  LNode *new_node;
  if ((new_node = __create_node(new_data, list->size)) == NULL) {
    return -1;
  }
  // 操作指针，需要两种情况，如果链表中没有数据，头尾指针是空的
  if (list->head_ptr != NULL && list->tail_ptr != NULL) {
    // 先操作new_node中的指针，因为不影响原数据
    new_node->prior = list->tail_ptr;
    new_node->next = list->head_ptr;
    // 将最后一个元素的next指针指向新元素
    list->tail_ptr->next = new_node;
    // 将第一个元素的prior指向新元素
    list->head_ptr->prior = new_node;
    // 头查法之后，头指针更新为新元素
    list->head_ptr = new_node;
  } else {
    // 如果是一个新链表，那么顺序就比较随意了
    // 大致的思路就是让头尾指针指向新元素
    // 之后将新元素的next、prior指向自己。
    list->head_ptr = new_node;
    list->tail_ptr = new_node;
    new_node->next = list->head_ptr;
    new_node->prior = list->tail_ptr;
  }
  list->nmemb++;
  return 1;
}
// 尾插法
int list_insert_back(LList *list, const void *new_data) {
  LNode *new_node;
  if ((new_node = __create_node(new_data, list->size)) == NULL) {
    return -1;
  }

  // 由于有了链表的尾节点，所以就不用通过循环遍历链表了
  if (list->head_ptr != NULL && list->tail_ptr != NULL) {
    new_node->next = list->head_ptr;
    new_node->prior = list->tail_ptr;
    list->tail_ptr->next = new_node;
    list->head_ptr->prior = new_node;
    list->tail_ptr = new_node;
  } else {
    list->tail_ptr = new_node;
    list->head_ptr = new_node;
    new_node->next = list->head_ptr;
    new_node->prior = list->tail_ptr;
  }
  list->nmemb++;
  return 1;
}
// 通过下标获取链表的元素，链表不像数组那样可以进行随机存取
// 获取数据需要封装一个新接口
void *list_get_data(const LList *list, size_t index) {
  if (list == NULL) {
    return NULL;
  }
  if (list->head_ptr == NULL) {
    return NULL;
  }
  LNode *ptr = list->head_ptr;
  while (index--) {
    ptr = ptr->next;
    if (ptr == NULL) {
      return NULL;
    }
  }
  return ptr->data;
}

// 通过数据寻找该节点的前一个节点，当时写单链表删除功能时定义的接口
// 如今已经不需要了，因为是双链表，
static struct LNode **__find_prev(LList *list, const void *key, cmp_t cmp) {
  // 二级指针获取头节点的指针
  // 有可能链表的第一个元素需要被删除，我们需要对LList结构的head_ptr成员进行操作
  // 而head_ptr是一个LNode* 类型，所以选择LNode **
  LNode **prev = &(list->head_ptr);
  // 这是cur初始化的值是 链表的第一个元素
  // 最开始写的是(*prev)->next，实际上这是第二个元素
  LNode *cur = (*prev);
  while (cur != NULL) {
    if (cmp(cur->data, key) == 0) {
      return prev;
    }
    if (cur->next != NULL || cur != NULL) {
      // 更新prev，将prev指向cur节点的next成员的地址
      prev = &(cur->next);
      cur = (*prev);
    } else {
      return NULL;
    }
  }
  return NULL;
}

// 重写一份更改适合双链表的静态查找接口
static struct LNode *__find(LList *list, const void *key, cmp_t cmp) {
  LNode *cur = list->head_ptr;
  size_t nmemb = list->nmemb;
  // 循环链表，通过元素个数控制循环
  // 或者是通过链表的头尾结点控制也可以
  // do{}while(cur!=list->head_ptr)在循环体中cur向下遍历
  while (nmemb--) {
    if (cmp(cur->data, key) == 0) {
      return cur;
    } else {

      cur = cur->next;
    }
  }
  return NULL;
}

static void __node_free(LNode **p) {
  free((*p)->data);
  (*p)->data = NULL;
  free(*p);
  *p = NULL;
}
int list_del_by_data(LList *list, const void *key, cmp_t cmp) {

  LNode *p = __find(list, key, cmp);
  if (p == NULL) {
    return -1;
  }

  // 有两种特殊情况，如果p是头尾节点么，需要重新指向头尾节点
  if (p == list->head_ptr) {
    list->head_ptr = p->next;
  }
  if (p == list->tail_ptr) {
    list->tail_ptr = p->prior;
  }
  // 在删除中需要改变的有，前驱节点的next 以及后继节点的prior
  p->prior->next = p->next;
  p->next->prior = p->prior;

  __node_free(&p);
  list->nmemb--;
  return 1;
}

int list_del_by_index(LList *list, size_t index) {
  LNode *p;
  if (index == 0) {
    p = list->head_ptr;
    list->head_ptr->next->prior = list->tail_ptr;
    list->tail_ptr->next = list->head_ptr->next;
  } else if (index == list->nmemb - 1) {
    p = list->tail_ptr;
    list->tail_ptr->prior->next = list->head_ptr;
    list->head_ptr->prior = list->tail_ptr->prior;
  } else {
    size_t temp_index = index;
    p = list->head_ptr;
    while (temp_index--) {
      p = p->next;
    }
    p->next->prior = p->prior;
    p->prior->next = p->next;
  }
  __node_free(&p);
  list->nmemb--;
  return 1;
}

int list_mod(LList *list, size_t index, void *new_data) {
  LNode *p = list->head_ptr;
  while (index--) {
    p = p->next;
  }
  memcpy(p->data, new_data, list->size);
  return 1;
}

void *list_search(const LList *list, const void *key, cmp_t cmp) {
  return __find(list, key, cmp);
}

void list_traval(const LList *list, pri_t pri) {
  LNode *index = list->head_ptr;
  // 由于是循环链表所以，此时通过空指针已经不能来控制遍历了
  // 所以引入链表元素的个数
  size_t nmemb = list->nmemb;
  while (index != NULL && nmemb--) {
    pri(index->data);
    index = index->next;
  }
}

void list_destory(LList **list) {
  LNode *del = (*list)->head_ptr;
  LNode *next_del = del->next;
  size_t temp = (*list)->nmemb;
  while (temp--) {
    __node_free(&del);
    del = next_del;
    next_del = next_del->next;
  }
  free(*list);
  *list = NULL;
}

void list_reverse(LList *list) {
  if (list == NULL || list->head_ptr == NULL || list->nmemb <= 1) {
    return;
  }

  LNode *current = list->head_ptr;
  do {
    // 交换 prior 和 next
    LNode *temp = current->prior;
    current->prior = current->next;
    current->next = temp;
    current = current->prior;
  } while (current != list->head_ptr);

  // 交换 head_ptr 和 tail_ptr
  LNode *temp = list->head_ptr;
  list->head_ptr = list->tail_ptr;
  list->tail_ptr = temp;
}
